Online Judge►LeetCode

[LeetCode] 124 - Binary Tree Maximum Path Sum

題意

求出一條路徑的和最大，起點和終點可以是任意點。

解法

對經過當前的node來說，最大路徑有下面幾種可能：

  1. node
  2. 左邊+node
  3. node+右邊
  4. 左邊+node+右邊

心得

乍看之下覺得似乎很簡單，但沒想到負數會這麼麻煩，也沒想到把最大值拉到外層就能解決許多問題 ..

程式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *	 int val;
 *	 TreeNode *left;
 *	 TreeNode *right;
 *	 TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
	int maxnum = -999999 ;
	int FindMax(TreeNode* node){
		if ( node == NULL )
			return 0 ;
		int left = FindMax(node->left) ;
		int right = FindMax(node->right) ;
		int nowmax = node->val ;
		if ( left > 0 )
			nowmax += left ;
		if ( right > 0 )
			nowmax += right ;
		if ( nowmax > maxnum )
			maxnum = nowmax ;
		return max(node->val,max(node->val+left,node->val+right)) ;
	}
	int maxPathSum(TreeNode* root) {
		FindMax(root) ;
		return maxnum ;
	}
};